package 路径总和;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 437. 路径总和 III  为解决
 * @date 2022/11/8 10:06
 */
public class Demo437 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(10);
        treeNode.left=new TreeNode(5);
        treeNode.right=new TreeNode(-3);
        treeNode.right.right=new TreeNode(11);
        treeNode.left.right=new TreeNode(2);
        treeNode.left.right.right=new TreeNode(1);
        treeNode.left.left=new TreeNode(3);
        treeNode.left.left.left=new TreeNode(3);
        treeNode.left.left.right=new TreeNode(-2);
        int i = pathSum(treeNode, 8);
        System.out.println(i);
    }
    public static int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
         //所有路径
        List<List<Integer>> res=new ArrayList<>();
        //单条路径
        List<Integer> singlePath=new ArrayList<>();
        //递归获取所有路径
        getPath(res,singlePath,root);
        int count=0;
        for (int i = 0; i < res.size(); i++) {
            List<Integer> list = res.get(i);
            while (list.size()>0){
                int sum=list.stream().mapToInt(s->s).sum();
                if(sum==targetSum){
                    count++;
                    break;
                }else {
                    list.remove(list.size()-1);
                }
            }
        }

          return count;
    }
    //递归函数
    private  static void getPath(List<List<Integer>> res, List<Integer> singlePath, TreeNode root) {
        singlePath.add(root.val);
        //返回条件
        if(root.left==null&&root.right==null){
            ArrayList<Integer> temp=new ArrayList(singlePath);
            res.add(temp);
            return;
        }
        if(root.left!=null){
            getPath(res,singlePath,root.left);
            //回溯
            singlePath.remove(singlePath.size()-1);
        }
        if(root.right!=null){
            getPath(res,singlePath,root.right);
            //回溯
            singlePath.remove(singlePath.size()-1);
        }
    }


    // Definition for a binary tree node.
     public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

}
